{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Parallel Courses II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #bit-manipulation #graph #dynamic-programming #bitmask"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #位运算 #图 #动态规划 #状态压缩"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: minNumberOfSemesters"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #并行课程 II"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个整数&nbsp;<code>n</code>&nbsp;表示某所大学里课程的数目，编号为&nbsp;<code>1</code>&nbsp;到&nbsp;<code>n</code>&nbsp;，数组&nbsp;<code>relations</code>&nbsp;中，&nbsp;<code>relations[i] = [x<sub>i</sub>, y<sub>i</sub>]</code>&nbsp; 表示一个先修课的关系，也就是课程&nbsp;<code>x<sub>i</sub></code>&nbsp;必须在课程&nbsp;<code>y<sub>i</sub></code><sub>&nbsp;</sub>之前上。同时你还有一个整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>在一个学期中，你 <strong>最多</strong>&nbsp;可以同时上 <code>k</code>&nbsp;门课，前提是这些课的先修课在之前的学期里已经上过了。</p>\n",
    "\n",
    "<p>请你返回上完所有课最少需要多少个学期。题目保证一定存在一种上完所有课的方式。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/06/27/leetcode_parallel_courses_1.png\" style=\"height: 164px; width: 300px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 4, relations = [[2,1],[3,1],[1,4]], k = 2\n",
    "<strong>输出：</strong>3 \n",
    "<strong>解释：</strong>上图展示了题目输入的图。在第一个学期中，我们可以上课程 2 和课程 3 。然后第二个学期上课程 1 ，第三个学期上课程 4 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><strong><img alt=\"\" src=\"https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/06/27/leetcode_parallel_courses_2.png\" style=\"height: 234px; width: 300px;\" /></strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 5, relations = [[2,1],[3,1],[4,1],[1,5]], k = 2\n",
    "<strong>输出：</strong>4 \n",
    "<strong>解释：</strong>上图展示了题目输入的图。一个最优方案是：第一学期上课程 2 和 3，第二学期上课程 4 ，第三学期上课程 1 ，第四学期上课程 5 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>n = 11, relations = [], k = 2\n",
    "<strong>输出：</strong>6\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= n &lt;= 15</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= n</code></li>\n",
    "\t<li><code>0 &lt;=&nbsp;relations.length &lt;= n * (n-1) / 2</code></li>\n",
    "\t<li><code>relations[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= x<sub>i</sub>, y<sub>i</sub>&nbsp;&lt;= n</code></li>\n",
    "\t<li><code>x<sub>i</sub> != y<sub>i</sub></code></li>\n",
    "\t<li>所有先修关系都是不同的，也就是说&nbsp;<code>relations[i] != relations[j]</code>&nbsp;。</li>\n",
    "\t<li>题目输入的图是个有向无环图。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [parallel-courses-ii](https://leetcode.cn/problems/parallel-courses-ii/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [parallel-courses-ii](https://leetcode.cn/problems/parallel-courses-ii/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['4\\n[[2,1],[3,1],[1,4]]\\n2', '5\\n[[2,1],[3,1],[4,1],[1,5]]\\n2']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        # 1. 递归\n",
    "        # pre1 = [0] * n \n",
    "        # for x, y in relations:\n",
    "        #     pre1[y - 1] |= 1 <<(x - 1) # y的先修课程集合， 下标改为从0开始\n",
    "        \n",
    "        # u = (1 << n) - 1 # 全集\n",
    "        # @cache\n",
    "        # def dfs(i:int) -> int:\n",
    "        #     if i == 0: #空集\n",
    "        #         return 0\n",
    "        #     ci = u ^ i # i的补集\n",
    "        #     i1 = 0\n",
    "        #     for j, p in enumerate(pre1): # 先修课程枚举\n",
    "        #         if i >> j & 1 and p | ci == ci: #p在i的补集中，可以学\n",
    "        #             i1 |= 1 << j\n",
    "        #     if i1.bit_count() <= k: #如果个数小于k， 则可以全部学习，不再枚举子集\n",
    "        #         return dfs(i ^ i1) + 1\n",
    "        #     res = inf\n",
    "        #     j = i1\n",
    "        #     while j: # 枚举i1的子集j\n",
    "        #         if j.bit_count() == k:\n",
    "        #             res = min(res, dfs(i ^ j) + 1)\n",
    "        #         j = (j - 1) & i1\n",
    "        #     return res\n",
    "        # return dfs(u)\n",
    "\n",
    "        # 2. 迭代\n",
    "        pre1 = [0] * n \n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1) # y的先修课程集合，下标改为从0开始\n",
    "        \n",
    "        u = (1 << n) - 1\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1, 1 << n):\n",
    "            ci = u ^ i # i的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci: # p在i的补集中，可以学\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k: #如果个数小于k，则可以全部学习，不再枚举子集\n",
    "                f[i]  = f[i ^ i1] + 1\n",
    "                continue\n",
    "            j = i1\n",
    "            while j: # 枚举i1的子集j\n",
    "                if j.bit_count() == k:\n",
    "                    f[i] = min(f[i], f[i ^ j] + 1)\n",
    "                j = (j - 1) & i1\n",
    "        return f[u]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        inf = float('inf')\n",
    "        pre = [0 for _ in range(n)]\n",
    "        for x, y in relations:\n",
    "            x -= 1\n",
    "            y -= 1\n",
    "            pre[y] |= (1 << x)\n",
    "        \n",
    "        dp = [inf for _ in range(1 << n)]\n",
    "        dp[0] = 0\n",
    "        for s in range(1, 1 << n):\n",
    "            rest = ((1 << n) - 1) & ~s\n",
    "            sel = 0\n",
    "            for i in range(n):\n",
    "                if (s >> i) & 1 == 1 and pre[i] | rest == rest:\n",
    "                    sel |= 1 << i\n",
    "\n",
    "            if sel.bit_count() <= k:\n",
    "                dp[s] = min(dp[s], dp[s ^ sel] + 1)\n",
    "            else:\n",
    "                sub = sel\n",
    "                while sub:\n",
    "                    if sub.bit_count() == k:\n",
    "                        dp[s] = min(dp[s], dp[s ^ sub] + 1)\n",
    "                    sub = (sub - 1) & sel\n",
    "        return dp[(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1, 1 << n):\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                f[i] = f[i ^ i1] + 1\n",
    "                continue\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    f[i] = min(f[i], f[i ^ j] + 1)\n",
    "                j = (j - 1) & i1\n",
    "        return f[u]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    递推写法\n",
    "    dp[i]表示学习二进制序列i代表的课程集合，最少需要多少个学期\n",
    "    因为i是本次所有要学的课程，但是能学的课程集合can_learn一定是i的子集（小于等于），所以遍历的顺序\n",
    "    是从小到大\n",
    "    '''\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        parent = [0] * n\n",
    "        for u, v in relations:\n",
    "            parent[v - 1] |= 1 << (u - 1)\n",
    "        \n",
    "        mask = (1 << n) - 1\n",
    "        dp = [float('inf')] * (1 << n)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, 1 << n):\n",
    "            learned = i ^ mask\n",
    "            can_learn = 0 \n",
    "            for j in range(n):\n",
    "                if i & (1 << j) and parent[j] | learned == learned:\n",
    "                    can_learn |= 1 << j\n",
    "            \n",
    "            if can_learn.bit_count() <= k:\n",
    "                dp[i] = dp[i ^ can_learn] + 1\n",
    "                continue\n",
    "            \n",
    "            j = can_learn\n",
    "            res = float('inf')\n",
    "            while j:\n",
    "                if j.bit_count() == k:\n",
    "                    dp[i] = min(dp[i], dp[i ^ j] + 1)\n",
    "                j = (j - 1) & can_learn\n",
    "            \n",
    "        return dp[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1, 1 << n):\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                f[i] = f[i ^ i1] + 1\n",
    "                continue\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    f[i] = min(f[i], f[i ^ j] + 1)\n",
    "                j = (j - 1) & i1\n",
    "        return f[u]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        '''#copy\n",
    "        pre1 = [0] * n\n",
    "        for x,y in relations:\n",
    "            pre1[y-1] |= 1<<(x-1)\n",
    "        \n",
    "        u = (1<<n)-1\n",
    "        f = [inf]*(1<<n)\n",
    "        f[0] = 0\n",
    "        for i in range(1,1<<n):\n",
    "            ci = u^i\n",
    "            i1 = 0\n",
    "            for j,p in enumerate(pre1):\n",
    "                if i >>j &1 and p|ci==ci:\n",
    "                    i1 |= 1<<j\n",
    "            if i1.bit_count()<=k:\n",
    "                f[i] = f[i^i1] +1\n",
    "                continue\n",
    "            j = i1\n",
    "            while j:\n",
    "                if j.bit_count() == k:\n",
    "                    f[i] = min(f[i],f[i^j] + 1)\n",
    "                j = (j-1)&i1\n",
    "            return f[u]'''"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        # 状态压缩dp： 子集枚举\n",
    "        # 1. dfs\n",
    "        # pre1 = [0] * n\n",
    "        # for x, y in relations:\n",
    "        #     pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        # u = (1 << n) - 1  # 全集\n",
    "        # @cache  # 记忆化搜索\n",
    "        # def dfs(i: int) -> int:\n",
    "        #     if i == 0:  # 空集\n",
    "        #         return 0\n",
    "        #     ci = u ^ i  # i 的补集\n",
    "        #     i1 = 0\n",
    "        #     for j, p in enumerate(pre1):\n",
    "        #         if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "        #             i1 |= 1 << j\n",
    "        #     if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "        #         return dfs(i ^ i1) + 1\n",
    "        #     res = inf\n",
    "        #     j = i1\n",
    "        #     while j:  # 枚举 i1 的子集 j\n",
    "        #         if j.bit_count() == k:\n",
    "        #             res = min(res, dfs(i ^ j) + 1)\n",
    "        #         j = (j - 1) & i1\n",
    "        #     return res\n",
    "        # return dfs(u)\n",
    "\n",
    "        # 2. 迭代：\n",
    "        pre1 = [0] * n \n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)\n",
    "\n",
    "        u = (1 << n) - 1\n",
    "        f = [inf] * (1 << n)\n",
    "        f[0] = 0\n",
    "        for i in range(1, 1 << n):\n",
    "            ci = u ^ i # i的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k: # 如果个数小于k，则可以全部学习，不在枚举\n",
    "                f[i] = f[i ^ i1] + 1\n",
    "                continue\n",
    "            j = i1\n",
    "            while j:\n",
    "                if j.bit_count() == k:\n",
    "                    f[i] = min(f[i], f[i ^ j] + 1)\n",
    "                j = (j - 1) & i1 \n",
    "        return f[u]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre[y - 1] |= 1 << (x - 1)\n",
    "        \n",
    "        dp = [inf] * (1 << n)\n",
    "        dp[0] = 0\n",
    "\n",
    "        for i in range(1, 1 << n):\n",
    "            # i以外的课全部上过了\n",
    "            l = 0\n",
    "            for j in range(n):\n",
    "                if (i >> j) & 1 and pre[j] & i == 0:\n",
    "                    l |= 1 << j\n",
    "            if l.bit_count() <= k:\n",
    "                dp[i] = dp[i ^ l] + 1\n",
    "                continue\n",
    "            j = l\n",
    "            while j:\n",
    "                if j.bit_count() <= k:\n",
    "                    dp[i] = min(dp[i], dp[i ^ j] + 1)\n",
    "                j = (j - 1) & l\n",
    "        return dp[(1 << n) - 1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "\n",
    "        pre1 = [0] * n\n",
    "        for x,y in relations:\n",
    "            pre1[y-1] |= 1<<(x-1)\n",
    "        \n",
    "        u = (1<<n)-1\n",
    "        f = [inf]*(1<<n)\n",
    "        f[0] = 0\n",
    "        for i in range(1,1<<n):\n",
    "            ci = u^i\n",
    "            i1 = 0\n",
    "            for j,p in enumerate(pre1):\n",
    "                if i >>j &1 and p|ci==ci:\n",
    "                    i1 |= 1<<j\n",
    "            if i1.bit_count()<=k:\n",
    "                f[i] = f[i^i1] +1\n",
    "                continue\n",
    "            j = i1\n",
    "            while j:\n",
    "                if j.bit_count() == k:\n",
    "                    f[i] = min(f[i],f[i ^  j] + 1)\n",
    "                j = (j-1) & i1\n",
    "        return f[u]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        g = defaultdict(list) \n",
    "        indeg = [0] * (n+1)\n",
    "        for a, b in relations:\n",
    "            g[a].append(b) \n",
    "            indeg[b] += 1\n",
    "        for i in range(1, n+1):\n",
    "            if indeg[i] == 0:\n",
    "                g[0].append(i)\n",
    "                indeg[i] += 1\n",
    "        dp = [float('inf')] * (1 << (n))\n",
    "        dp[0] = 0\n",
    "        def bit_count(x):\n",
    "            cnt = 0\n",
    "            for i in range(n):\n",
    "                if (x >> i)&1:\n",
    "                    cnt +=1\n",
    "            return cnt \n",
    "\n",
    "        for i in range(1<<n):\n",
    "            if dp[i] != float('inf'):\n",
    "                Q = {0}\n",
    "                for j in range(n):\n",
    "                    if (i >> j) & 1:\n",
    "                        Q.add(j+1) \n",
    "                s = 0\n",
    "                indegree = copy.deepcopy(indeg)\n",
    "                for x in Q:\n",
    "                    for y in g[x]:\n",
    "                        indegree[y] -= 1\n",
    "                        if indegree[y] == 0 and y not in Q:\n",
    "                            s |=(1 << (y-1))\n",
    "\n",
    "                if bit_count(s) <= k:\n",
    "                    dp[i|s] = min(dp[i|s], dp[i]+1)\n",
    "                else:\n",
    "                    j = (s-1)&s \n",
    "                    while j > 0:\n",
    "                        if bit_count(j) == k:\n",
    "                            dp[i|j] = min(dp[i|j], dp[i] + 1)\n",
    "                        j = (j-1) & s\n",
    "        return dp[(1<<n) -1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0]*n\n",
    "        for x,y in relations:\n",
    "            pre1[y-1] |= 1<<(x-1)\n",
    "        \n",
    "        u= (1<<n)-1\n",
    "        f=[inf]*(1<<n)\n",
    "        f[0]=0\n",
    "\n",
    "        for i in range(1,1<<n):\n",
    "            ci = u^i\n",
    "            i1=0\n",
    "            for j,p in enumerate(pre1):\n",
    "                #该课程还没有学，且先修课已经学过了\n",
    "                if i>>j&1 and p|ci ==ci:\n",
    "                    i1 |= 1<<j\n",
    "                #集合里的课程可以在一个学期里学完\n",
    "            if i1.bit_count()<=k:\n",
    "                f[i] =f[i^i1] +1\n",
    "                continue\n",
    "            j =i1\n",
    "            while j:\n",
    "                if j.bit_count()==k:\n",
    "                    f[i] = min(f[i],f[i^j]+1)\n",
    "                j = (j-1)&i1 #从大到小枚举i1的所有非空子集\n",
    "\n",
    "        return f[u]\n",
    "\n",
    "                    \n",
    "\n",
    "                     \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        u = 1 << n\n",
    "        val = [0] * (u)\n",
    "        for i in range(u):\n",
    "            j = i\n",
    "            while j:\n",
    "                #print(i, j)\n",
    "                val[i] += 1\n",
    "                j = j & (j - 1)\n",
    "        #print(val)\n",
    "        pre = [0] * n\n",
    "        for a, b in relations:\n",
    "            pre[(b - 1)] |= (1 << (a - 1))\n",
    "        f = [inf] * u\n",
    "        f[0] = 0\n",
    "        for i in range(u):\n",
    "            cui = (u - 1) ^ i\n",
    "            i0 = 0\n",
    "            for j, x in enumerate(pre):\n",
    "                if cui >> j & 1 and (x | i) == i:\n",
    "                    i0 |= (1 << j)\n",
    "            \n",
    "            tar = i | i0\n",
    "            #print(i, i0, tar)\n",
    "            if val[i0] <= k:\n",
    "                f[tar] = min(f[tar], f[i] + 1)\n",
    "                continue\n",
    "            j = i0 - 1\n",
    "            while j:\n",
    "                tar = j | i\n",
    "                if val[j] == k:\n",
    "                    f[tar] = min(f[tar], f[i] + 1)\n",
    "                j = (j - 1) & i0\n",
    "        #print(f)\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        parent = [0] * n\n",
    "        for u, v in relations:\n",
    "            parent[v - 1] |= 1 << (u - 1)\n",
    "        \n",
    "        mask = (1 << n) - 1\n",
    "        dp = [float('inf')] * (1 << n)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, 1 << n):\n",
    "            learned = i ^ mask\n",
    "            can_learn = 0 \n",
    "            for j in range(n):\n",
    "                if i & (1 << j) and parent[j] | learned == learned:\n",
    "                    can_learn |= 1 << j\n",
    "            \n",
    "            if can_learn.bit_count() <= k:\n",
    "                dp[i] = dp[i ^ can_learn] + 1\n",
    "                continue\n",
    "            \n",
    "            j = can_learn\n",
    "            res = float('inf')\n",
    "            while j:\n",
    "                if j.bit_count() == k:\n",
    "                    dp[i] = min(dp[i], dp[i ^ j] + 1)\n",
    "                j = (j - 1) & can_learn\n",
    "            \n",
    "        return dp[-1]\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        u = 1 << n\n",
    "        val = [0] * (u)\n",
    "        for i in range(u):\n",
    "            j = i\n",
    "            while j:\n",
    "                #print(i, j)\n",
    "                val[i] += 1\n",
    "                j = j & (j - 1)\n",
    "        #print(val)\n",
    "        pre = [0] * n\n",
    "        for a, b in relations:\n",
    "            pre[(b - 1)] |= (1 << (a - 1))\n",
    "        f = [inf] * u\n",
    "        f[0] = 0\n",
    "        for i in range(u):\n",
    "            cui = (u - 1) ^ i\n",
    "            i0 = 0\n",
    "            for j, x in enumerate(pre):\n",
    "                if cui >> j & 1 and (x | i) == i:\n",
    "                    i0 |= (1 << j)\n",
    "            \n",
    "            tar = i | i0\n",
    "            #print(i, i0, tar)\n",
    "            if val[i0] <= k:\n",
    "                f[tar] = min(f[tar], f[i] + 1)\n",
    "                continue\n",
    "            j = i0 - 1\n",
    "            while j:\n",
    "                tar = j | i\n",
    "                if val[j] <= k:\n",
    "                    f[tar] = min(f[tar], f[i] + 1)\n",
    "                j = (j - 1) & i0\n",
    "        #print(f)\n",
    "        return f[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import *\n",
    "from math import *\n",
    "from functools import cache\n",
    "from queue import *\n",
    "from heapq import *\n",
    "from itertools import *\n",
    "from bisect import bisect_left\n",
    "# start-----------------------------------------------------\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre[y - 1] |= 1 << (x - 1)\n",
    "        u = (1 << n) - 1\n",
    "\n",
    "        @cache\n",
    "        def f(i:int) -> int:\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            c = u ^ i\n",
    "            i2 = 0\n",
    "            for j, p in enumerate(pre):\n",
    "                if (i >> j) & 1 and p | c == c:\n",
    "                    i2 |= 1 << j\n",
    "            if i2.bit_count() <= k:\n",
    "                return f(i ^ i2) + 1\n",
    "            res = inf\n",
    "            j = i2\n",
    "            while j:\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, f(i ^ j) + 1)\n",
    "                j = (j - 1) & i2\n",
    "            return res\n",
    "        return f(u)\n",
    "\n",
    "# end-------------------------------------------------------\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in relations:\n",
    "            g[y - 1].append(x - 1)\n",
    "        u = (1 << n) - 1\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            takes = []\n",
    "            for j in range(n):\n",
    "                flag = True\n",
    "                if (i >> j) & 1:\n",
    "                    for adj in g[j]:\n",
    "                        if (i >> adj) & 1:\n",
    "                            break\n",
    "                    else: takes.append(j)\n",
    "            ans = 16\n",
    "            if len(takes) <= k:\n",
    "                mask = i\n",
    "                for x in takes:\n",
    "                    mask ^= (1 << x)\n",
    "                ans = min(ans, dfs(mask) + 1)\n",
    "                return ans\n",
    "            else:\n",
    "                for perm in combinations(takes, k):\n",
    "                    mask = i\n",
    "                    for x in perm:\n",
    "                        mask ^= (1 << x)\n",
    "                    ans = min(ans, dfs(mask) + 1)\n",
    "                return ans\n",
    "        return dfs(u)\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre[y - 1] |= 1 << (x - 1)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if state.bit_count() == n:\n",
    "                return 0\n",
    "            \n",
    "            c = 0\n",
    "            for i, p in enumerate(pre):\n",
    "                if state & 1 << i == 0 and p & state == p:\n",
    "                    c |= 1 << i\n",
    "            \n",
    "            if c.bit_count() <= k:\n",
    "                return 1 + dfs(state | c)\n",
    "            \n",
    "            res = inf\n",
    "            # 枚举子集\n",
    "            x = c\n",
    "            while x:\n",
    "                if x.bit_count() == k:\n",
    "                    res = min(res, 1 + dfs(state | x))\n",
    "                x = (x - 1) & c\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "\n",
    "        par = [0 for _ in range(n)]\n",
    "\n",
    "        for x, y in relations:\n",
    "            par[y-1] |= 1 << (x-1)\n",
    "\n",
    "        comb = []   #能选的k个组合\n",
    "        chosed = 0  #选择了哪些课程\n",
    "\n",
    "        def choose(can_use, k, i):\n",
    "            nonlocal chosed\n",
    "            if k == 0:\n",
    "                comb.append(chosed)\n",
    "                return \n",
    "\n",
    "            if i == n:\n",
    "                return \n",
    "\n",
    "            for j in range(i, n):\n",
    "                if (can_use >> j) & 1:\n",
    "                    \n",
    "                    choose(can_use, k, j+1)\n",
    "\n",
    "                    chosed |= 1 << j\n",
    "                    choose(can_use ^ (1 << j), k-1, i+1)\n",
    "                    chosed ^= 1 << j\n",
    "            \n",
    "        @cache\n",
    "        def dfs(learned):\n",
    "            if learned == (1 << n) - 1:\n",
    "                return 0\n",
    "\n",
    "            can_learn = 0\n",
    "            for i in range(n):\n",
    " \n",
    "                if (learned >> i) & 1:\n",
    "                    continue\n",
    "                if learned & par[i] == par[i]:\n",
    "                    can_learn |= 1 << i\n",
    "\n",
    "            if can_learn.bit_count() <= k:\n",
    "                return 1 + dfs(learned | can_learn)\n",
    "            \n",
    "            day = inf\n",
    "            j = can_learn\n",
    "            while j:\n",
    "                if j.bit_count() == k:\n",
    "                    day = min(day, dfs(learned | j))\n",
    "                j = (j - 1) & can_learn\n",
    "            return day + 1    \n",
    "\n",
    "\n",
    "        return dfs(0)\n",
    "\n",
    "\n",
    "                \n",
    "                    \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                    \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        DONE = (1<<n)-1\n",
    "        pre = [0]*n\n",
    "        for a,b in relations:\n",
    "            pre[b-1] |= 1<<(a-1)\n",
    "\n",
    "        @functools.cache\n",
    "        def dp(state):\n",
    "            if state == DONE:\n",
    "                return 0\n",
    "            \n",
    "            ready = [i for i in range(n) if pre[i]&state==pre[i] and (state>>i)&1==0]\n",
    "            res = math.inf\n",
    "            for takes in itertools.combinations(ready, min(k,len(ready))):\n",
    "                res = min(res, 1+dp(functools.reduce(lambda a,b: a|(1<<b),takes,state)))\n",
    "            return res\n",
    "\n",
    "        return dp(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in relations:\n",
    "            g[y - 1].append(x - 1)\n",
    "        u = (1 << n) - 1\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            takes = []\n",
    "            for j in range(n):\n",
    "                flag = True\n",
    "                if (i >> j) & 1:\n",
    "                    for adj in g[j]:\n",
    "                        if (i >> adj) & 1:\n",
    "                            break\n",
    "                    else: takes.append(j)\n",
    "            ans = 16\n",
    "            if len(takes) <= k:\n",
    "                mask = i\n",
    "                for x in takes:\n",
    "                    mask ^= (1 << x)\n",
    "                return dfs(mask) + 1\n",
    "            else:\n",
    "                for perm in combinations(takes, k):\n",
    "                    mask = i\n",
    "                    for x in perm:\n",
    "                        mask ^= (1 << x)\n",
    "                    ans = min(ans, dfs(mask) + 1)\n",
    "                return ans\n",
    "        return dfs(u)\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre[y - 1] |= 1 << (x - 1)\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if state.bit_count() == n:\n",
    "                return 0\n",
    "            \n",
    "            c = 0\n",
    "            for i, p in enumerate(pre):\n",
    "                if p & state == p and state & 1 << i == 0:\n",
    "                    c |= 1 << i\n",
    "            if c.bit_count() <= k:\n",
    "                return 1 + dfs(state | c)\n",
    "            \n",
    "            res = inf\n",
    "            x = c\n",
    "            while x:\n",
    "                if x.bit_count() == k:\n",
    "                    res = min(res, 1 + dfs(state | x))\n",
    "                x = (x - 1) & c\n",
    "            return res\n",
    "\n",
    "        ans = dfs(0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        dp = [inf] * (1 << n)\n",
    "        need = [0] * (1 << n)\n",
    "        for edge in relations:\n",
    "            need[(1 << (edge[1] - 1))] |= 1 << (edge[0] - 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, (1 << n)):\n",
    "            need[i] = need[i & (i - 1)] | need[i & (-i)]\n",
    "            if (need[i] | i) != i: # i 中有任意一门课程的前置课程没有完成学习\n",
    "                continue\n",
    "            sub = valid = i ^ need[i] # 当前学期可以进行学习的课程集合\n",
    "            if sub.bit_count() <= k: # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                dp[i] = min(dp[i], dp[i ^ sub] + 1)\n",
    "            else: # 枚举子集\n",
    "                while sub:\n",
    "                    if sub.bit_count() <= k:\n",
    "                        dp[i] = min(dp[i], dp[i ^ sub] + 1)\n",
    "                    sub = (sub - 1) & valid\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        d = [0] * (n + 1)\n",
    "        for x, y in relations:\n",
    "            d[y] |= 1 << x\n",
    "        q = deque([(0, 0)])\n",
    "        vis = {0}\n",
    "        while q:\n",
    "            cur, t = q.popleft()\n",
    "            if cur == (1 << (n + 1)) - 2:\n",
    "                return t\n",
    "            nxt = 0\n",
    "            for i in range(1, n + 1):\n",
    "                if (cur & d[i]) == d[i]:\n",
    "                    nxt |= 1 << i\n",
    "            nxt ^= cur\n",
    "            if nxt.bit_count() <= k:\n",
    "                if (nxt | cur) not in vis:\n",
    "                    vis.add(nxt | cur)\n",
    "                    q.append((nxt | cur, t + 1))\n",
    "            else:\n",
    "                x = nxt\n",
    "                while nxt:\n",
    "                    if nxt.bit_count() == k and (nxt | cur) not in vis:\n",
    "                        vis.add(nxt | cur)\n",
    "                        q.append((nxt | cur, t + 1))\n",
    "                    nxt = (nxt - 1) & x"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "\n",
    "       \n",
    "        dp = [float(\"inf\")]*(1<<n)\n",
    "        dp[0] = 0\n",
    "        need = [0]*(1<<n)\n",
    "        for x,y in relations:\n",
    "            need[1<<(y-1)] |= 1<<(x-1)\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        for i in range(1,1<<n):\n",
    "            if i.bit_count()>1:\n",
    "                prev = i&(i-1)\n",
    "                need[i] = need[prev] | need[i-prev]\n",
    "            if need[i]& i !=need[i]:\n",
    "                continue \n",
    "\n",
    "            sub = valid = i^need[i]\n",
    "            if sub.bit_count()<=k:\n",
    "                dp[i] = min(dp[i], dp[i ^ sub] + 1)\n",
    "\n",
    "            while sub:\n",
    "                if sub.bit_count()<=k:\n",
    "                    \n",
    "\n",
    "                    dp[i] = min(dp[i], dp[i^sub]+1)\n",
    "\n",
    "                sub = (sub-1)&valid\n",
    "        \n",
    "        return dp[(1<<n)-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        d = [0] * (n + 1)\n",
    "        for x, y in relations:\n",
    "            d[y] |= 1 << x\n",
    "        q = deque([(0, 0)])\n",
    "        vis = {0}\n",
    "        while q:\n",
    "            cur, t = q.popleft()\n",
    "            if cur == (1 << (n + 1)) - 2:\n",
    "                return t\n",
    "            nxt = 0\n",
    "            for i in range(1, n + 1):\n",
    "                if (cur & d[i]) == d[i]:\n",
    "                    nxt |= 1 << i\n",
    "            nxt ^= cur\n",
    "            if nxt.bit_count() <= k:\n",
    "                if (nxt | cur) not in vis:\n",
    "                    vis.add(nxt | cur)\n",
    "                    q.append((nxt | cur, t + 1))\n",
    "            else:\n",
    "                x = nxt\n",
    "                while nxt:\n",
    "                    if nxt.bit_count() == k and (nxt | cur) not in vis:\n",
    "                        vis.add(nxt | cur)\n",
    "                        q.append((nxt | cur, t + 1))\n",
    "                    nxt = (nxt - 1) & x\n",
    "\n",
    "\\"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        # 1. dfs\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "\n",
    "        pre = [0] * n\n",
    "        degree = [0] * n\n",
    "        dct = [[] for _ in range(n)]\n",
    "        for i, j in relations:\n",
    "            i -= 1\n",
    "            j -= 1\n",
    "            dct[i].append(j)\n",
    "            degree[j] += 1\n",
    "        stack = [i for i in range(n) if not degree[i]]\n",
    "        while stack:\n",
    "            nex = []\n",
    "            for i in stack:\n",
    "                for j in dct[i]:\n",
    "                    degree[j] -= 1\n",
    "                    pre[j] |= (pre[i] | (1 << i))\n",
    "                    if not degree[j]:\n",
    "                        nex.append(j)\n",
    "            stack = nex[:]\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(state):\n",
    "            if not state:\n",
    "                return 0\n",
    "\n",
    "            lst = [i for i in range(n) if pre[i] & state == 0 and state & (1<<i)]\n",
    "            res = inf\n",
    "            y = min(len(lst), k)\n",
    "            for item in combinations(lst, y):\n",
    "                s = reduce(or_, [(1 << xx) for xx in item])\n",
    "                cur = 1 + dfs(state ^ s)\n",
    "                if cur < res:\n",
    "                    res = cur\n",
    "            return res\n",
    "\n",
    "        return dfs((1 << n) - 1)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        \"\"\"\n",
    "        只能上入度为0的课程\n",
    "        上完某一门课 就可以消除依赖关系 但这也存在一个问题就是不能盲目选择 \n",
    "        比如有 0 1 2 3共4门课 2依赖 1 3，k=2 则先修1 3 再修0 2，只需要2个学期 如果先修了0 就需要三个学期 \n",
    "        解法：\n",
    "        用S代表目前还需学习的课程，S第i位为1则代表需要学习\n",
    "        dp[i]代表学习集合为i的课程所需要的最少学期 初始为inf 代表该课程集合无法完成学习\n",
    "        need[i]代表完成集合i所需要的先修课程集合\n",
    "        初始 dp[0]=0 need[0]=0\n",
    "        状态转移方程：课程重新编号为0~n-1\n",
    "        need[i] = need[i^sub] | need[sub]\n",
    "        dp[i] = min dp[i^sub]+1 if sub is valid\n",
    "        sub是i的任意一个子集，i的先修课程为 集合sub的先修课和i去掉sub的先修课 的并集\n",
    "        对于dp[i]不断的去枚举子集sub 使得dp[i]最小 但枚举的时候需要满足条件\n",
    "            1.sub大小要小于等于k\n",
    "            2.剩下课程集合i^sub可以在有限课程完成即dp[i^sub]!=inf\n",
    "            3.剩下课程集合i^sub不存在sub的先修课即need[sub]&(i^sub)=need[sub]\n",
    "        \"\"\"\n",
    "        dp = [inf for _ in range(1<<n)]#有2^n个状态 每一门课可以选择也可以不选择\n",
    "        need = [0 for _ in range(1<<n)]\n",
    "        for edge in relations:\n",
    "            need[1<<(edge[1]-1)] |= 1<<(edge[0]-1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1,1<<n):\n",
    "            need[i] = need[i&(i-1)] | need[i&(-i)]\n",
    "            if need[i] | i != i:# i 中有任意一门课程的前置课程没有完成学习\n",
    "                continue\n",
    "            sub = valid = i ^ need[i] # 当前学期可以进行学习的课程集合\n",
    "            if sub.bit_count() <= k: # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                dp[i] = min(dp[i], dp[i ^ sub] + 1)\n",
    "            else:# 枚举子集\n",
    "                while sub:\n",
    "                    if sub.bit_count() <= k:\n",
    "                        dp[i] = min(dp[i], dp[i ^ sub] + 1)\n",
    "                    sub = (sub - 1) & valid\n",
    "        return dp[-1]\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre = [0] * n \n",
    "        for a, b in relations:\n",
    "            pre[b-1] |= 1 << (a - 1)\n",
    "        \n",
    "        u = (1 << n) - 1\n",
    "\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            \n",
    "            ci = u ^ i\n",
    "            a = 0\n",
    "            for x, y in enumerate(pre):\n",
    "                if (1 << x) & i != 0 and (y | ci) == ci:\n",
    "                    a |= (1 << x)\n",
    "            \n",
    "            if a.bit_count() <= k:\n",
    "                return dfs(i ^ a) + 1\n",
    "            \n",
    "            t = (a - 1) & a\n",
    "            res = int(1e9)\n",
    "            while t > 0:\n",
    "                if t.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ t))\n",
    "                t = (t - 1) & a\n",
    "            \n",
    "            return res + 1\n",
    "        \n",
    "        return dfs(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    状压DP，递归写法\n",
    "    为什么这条题目不用图相关的拓扑排序写法，我理解是因为题目中多了k的限制，假设拓扑排序后某一层有5个课程，\n",
    "    限制了同时最多上2门课，其实是需要枚举候选的5门课中任意的2门课组合的，拓扑排序再出来这个就很麻烦\n",
    "    由于课程数限制在15以内，因此可以考虑用状态压缩，将二进制的每一位认为是一门课程，1表示需要学习，0表示已经\n",
    "    学习过了，所有需要学习的课程二进制组合，所依赖的前置课程必定在这个二进制组合对应位为0的那些课程里（子集），\n",
    "    当我们要求学习某个课程组合需要的最小学期数时，我们就得保证这些需要学习的课程的前置课程必须满足这个条件\n",
    "    定义helper(i)表示要学习i对应的二级制课程组合时需要的最小学期数\n",
    "    '''\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        '''\n",
    "        将学习课程i所需要的所有“直接”前置课程列出来\n",
    "        为了二进制处理方便，将从1开始的课程变成从0开始保存\n",
    "        '''\n",
    "        parent = [0] * n\n",
    "        for u, v in relations:\n",
    "            parent[v - 1] |= 1 << (u - 1)\n",
    "        ''' \n",
    "        由于任何要学习的课程二进制组合对应的所有已学习课程都是其补集，而我们要根据这个已学习课程，判断\n",
    "        当前要学习的课程能否学习，求补集需要全量课程的二进制掩码\n",
    "        ''' \n",
    "        limit = (1 << n) - 1\n",
    "\n",
    "        @cache\n",
    "        def helper(course):\n",
    "            if not course:\n",
    "                return 0\n",
    "            learned = limit ^ course \n",
    "            can_learn = 0\n",
    "            for i in range(n):\n",
    "                '''\n",
    "                遍历所有课程，如果课程是当前需要学习的，且该课程的所有前置课程都已经学习过，\n",
    "                那么这个要学习的课程本次就可以学习\n",
    "                '''\n",
    "                if course & (1 << i) and parent[i] | learned == learned:\n",
    "                    can_learn |= 1 << i\n",
    "            ''' \n",
    "            此时得到所有本轮可以学习的课程，如果这些课程总数小于k的限制，那么可以一起学了\n",
    "            '''\n",
    "            if can_learn.bit_count() <= k:\n",
    "                return helper(course ^ can_learn) + 1\n",
    "            ''' \n",
    "            否则就要从可以学习课程的组合中枚举所有只学习k门课程的组合\n",
    "            这里二进制枚举所有子集的方法学习一下\n",
    "            ''' \n",
    "            res = float('inf')\n",
    "            j = can_learn\n",
    "            while j:\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, helper(course ^ j) + 1)\n",
    "                j = (j - 1) & can_learn\n",
    "            return res\n",
    "        \n",
    "        return helper(limit)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        dp = [inf] * (1 << n)\n",
    "        need = [0] * (1 << n)\n",
    "        for edge in relations:\n",
    "            need[1 << (edge[1] - 1)] |= 1 << (edge[0] - 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, (1 << n)):\n",
    "            need[i] = need[i & (i - 1)] | need[i & -i]\n",
    "            if (need[i] | i) != i:\n",
    "                continue\n",
    "            sub = valid = i ^ need[i]\n",
    "            if sub.bit_count() <= k:\n",
    "                dp[i] = min(dp[i], dp[i ^ sub] + 1)\n",
    "            else:\n",
    "                while sub:\n",
    "                    if sub.bit_count() <= k:\n",
    "                        dp[i] = min(dp[i], dp[i ^ sub] + 1)\n",
    "                    sub = (sub - 1) & valid\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        u = (1 << n) - 1\n",
    "        pre = [0] * n\n",
    "        for a, b in relations:\n",
    "            pre[b - 1] |= (1 << (a - 1))\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0: return 0\n",
    "            cui = u ^ i\n",
    "            i1 = 0\n",
    "            res = inf\n",
    "            for j, val in enumerate(pre):\n",
    "                if i >> j & 1 and val | cui == cui:\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k: return dfs(i ^ i1) + 1\n",
    "            j = i1 - 1\n",
    "            while j:\n",
    "                if j.bit_count() == k: res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n \n",
    "        for x ,y in relations:\n",
    "            pre1[y-1] |= 1 << (x-1)\n",
    "        \n",
    "        u = (1 << n) - 1\n",
    "        @cache \n",
    "        def dfs(i):\n",
    "            if i == 0:\n",
    "                return 0 \n",
    "            ci = u ^ i \n",
    "            i1 = 0 \n",
    "            for j,p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:\n",
    "                    i1 |= 1 << j \n",
    "            \n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n",
    "         "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        dp = [inf] * (1 << n)\n",
    "        need = [0] * (1 << n)\n",
    "        for edge in relations:\n",
    "            need[(1 << (edge[1] - 1))] |= 1 << (edge[0] - 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, (1 << n)):\n",
    "            need[i] = need[i & (i - 1)] | need[i & (-i)]\n",
    "            if (need[i] | i) != i: # i 中有任意一门课程的前置课程没有完成学习\n",
    "                continue\n",
    "            sub = valid = i ^ need[i] # 当前学期可以进行学习的课程集合\n",
    "            if sub.bit_count() <= k: # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                dp[i] = min(dp[i], dp[i ^ sub] + 1)\n",
    "            else: # 枚举子集\n",
    "                while sub:\n",
    "                    if sub.bit_count() <= k:\n",
    "                        dp[i] = min(dp[i], dp[i ^ sub] + 1)\n",
    "                    sub = (sub - 1) & valid\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        dp = [float('inf')] * (1 << n)\n",
    "        need = [0] * (1 << n)\n",
    "        for edge in relations:\n",
    "            need[1<<(edge[1]-1)] |= 1 << (edge[0] - 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, 1 << n):\n",
    "            need[i] = need[i & (i-1)] | need[i & (-i)]\n",
    "            if (need[i] | i) != i:\n",
    "                continue\n",
    "            sub = valid = i^need[i]\n",
    "            if sub.bit_count() <= k:\n",
    "                dp[i] = min(dp[i], dp[i^sub] + 1)\n",
    "            else:\n",
    "                while sub:\n",
    "                    if sub.bit_count() <= k:\n",
    "                        dp[i] = min(dp[i], dp[i^sub] + 1)\n",
    "                    sub = (sub-1) & valid\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        parent = [0] * n\n",
    "        for u, v in relations:\n",
    "            parent[v - 1] |= 1 << (u - 1)\n",
    "        \n",
    "        limit = (1 << n) - 1\n",
    "\n",
    "        @cache\n",
    "        def helper(course):\n",
    "            if not course:\n",
    "                return 0\n",
    "            learned = limit ^ course \n",
    "            can_learn = 0\n",
    "            for i in range(n):\n",
    "                if course & (1 << i) and parent[i] | learned == learned:\n",
    "                    can_learn |= 1 << i\n",
    "            \n",
    "            if can_learn.bit_count() <= k:\n",
    "                return helper(course ^ can_learn) + 1\n",
    "            \n",
    "            res = float('inf')\n",
    "            j = can_learn\n",
    "            while j:\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, helper(course ^ j) + 1)\n",
    "                j = (j - 1) & can_learn\n",
    "            return res\n",
    "        \n",
    "        return helper(limit)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        dp = [inf] * (1 << n)\n",
    "        need = [0] * (1 << n)\n",
    "        for edge in relations:\n",
    "            need[(1 << (edge[1] - 1))] |= 1 << (edge[0] - 1) #每门课程的前置条件\n",
    "        dp[0] = 0\n",
    "        for i in range(1, (1 << n)): #遍历所有可能，\n",
    "            need[i] = need[i & (i - 1)] | need[i & (-i)]\n",
    "            if (need[i] | i) != i: # 集合i 中包含课程及课程的所有前置课程，否则集合i永远无法学习完成，此时dp[i]值=inf不变。\n",
    "                continue\n",
    "            sub = valid = i ^ need[i] # need[i]在i中的补集，该集合中所有非前置课程，既集合i最后一个学期学习得课程。\n",
    "            if sub.bit_count() <= k: # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                dp[i] = dp[i ^ sub] + 1#dp[i]=dp[i ^ sub]+1，这里无需取min？\n",
    "            else: # 向下枚举子集\n",
    "                while sub:\n",
    "                    if sub.bit_count() <= k:\n",
    "                        dp[i] = min(dp[i], dp[i ^ sub] + 1)#取子集中解的最小值\n",
    "                    sub = (sub - 1) & valid\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "\n",
    "    \n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p & ci == p:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                    \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                    \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                \n",
    "                    \n",
    "\n",
    "\n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        dp = [inf] * (1 << n)\n",
    "        need = [0] * (1 << n)\n",
    "        for edge in relations:\n",
    "            need[(1 << (edge[1] - 1))] |= 1 << (edge[0] - 1) #每门课程的前置课程，在bit位时，i只有一种课程，填入need中\n",
    "        dp[0] = 0\n",
    "        for i in range(1, (1 << n)): #向上遍历n得所有子集\n",
    "            need[i] = need[i & (i - 1)] | need[i & (-i)]#求解所有得need[i]\n",
    "            if (need[i] | i) != i: # 集合i 中包含课程及课程的所有前置课程，否则集合i永远无法学习完成，此时dp[i]值=inf不变。\n",
    "                continue\n",
    "            sub = valid = i ^ need[i] # need[i]在i中的补集，该集合中所有非前置课程，既集合i最后一个学期学习得课程。\n",
    "            \n",
    "            if sub.bit_count() <= k: # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                dp[i] = dp[i ^ sub] + 1#dp[i]=dp[i ^ sub]+1，这里无需取min？dp[i ^ sub]作为i得子集一定在前面得遍历中被计算出来了\n",
    "            else: # 向下枚举sub得所有子集\n",
    "                while sub:#sub为非空子集\n",
    "                    if sub.bit_count() <= k:\n",
    "                        dp[i] = min(dp[i],dp[i ^ sub] + 1)#取子集中解的最小值\n",
    "\n",
    "                    sub = (sub - 1) & valid#确保sub'一定为sub得子集\n",
    "        return dp[-1]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        # 1. 递归\n",
    "        pre1 = [0] * n \n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 <<(x - 1) # y的先修课程集合， 下标改为从0开始\n",
    "        \n",
    "        u = (1 << n) - 1 # 全集\n",
    "        @cache\n",
    "        def dfs(i:int) -> int:\n",
    "            if i == 0: #空集\n",
    "                return 0\n",
    "            ci = u ^ i # i的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1): # 先修课程枚举\n",
    "                if i >> j & 1 and p | ci == ci: #p在i的补集中，可以学\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k: #如果个数小于k， 则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j: # 枚举i1的子集j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        dp = [inf] * (1 << n)\n",
    "        need = [0] * (1 << n)\n",
    "        for edge in relations:\n",
    "            need[(1 << (edge[1] - 1))] |= 1 << (edge[0] - 1)\n",
    "        dp[0] = 0\n",
    "        for i in range(1, (1 << n)):\n",
    "            need[i] = need[i & (i - 1)] | need[i & (-i)]\n",
    "            if (need[i] | i) != i: # i 中有任意一门课程的前置课程没有完成学习\n",
    "                continue\n",
    "            sub = valid = i ^ need[i] # 当前学期可以进行学习的课程集合\n",
    "            if sub.bit_count() <= k: # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                dp[i] = min(dp[i], dp[i ^ sub] + 1)\n",
    "            else: # 枚举子集\n",
    "                while sub:\n",
    "                    if sub.bit_count() <= k:\n",
    "                        dp[i] = min(dp[i], dp[i ^ sub] + 1)\n",
    "                    sub = (sub - 1) & valid\n",
    "        return dp[-1]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre=[0]*n\n",
    "        for x,y in relations:\n",
    "            pre[y-1]|=1<<(x-1)\n",
    "        u=(1<<n)-1\n",
    "        @cache\n",
    "        def dfs(i)->int:\n",
    "            if i==0:return 0\n",
    "            c=u^i\n",
    "            i1=0\n",
    "            for j,p in enumerate(pre):\n",
    "                if i>>j&1 and p|c==c:\n",
    "                    i1|=1<<j\n",
    "            if i1.bit_count()<=k:\n",
    "                return dfs(i^i1)+1\n",
    "            res=inf\n",
    "            j=i1\n",
    "            while j:\n",
    "                if j.bit_count()==k:\n",
    "                    res=min(res,dfs(i^j)+1)\n",
    "                j=(j-1)&i1\n",
    "            return res\n",
    "        return dfs(u)\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        @lru_cache(None)\n",
    "\n",
    "        def dfs(state):\n",
    "            if state == (1 << n) - 1:\n",
    "                return 0\n",
    "            nex = [i for i in range(n) if not state & (1 << i) and state & pre[i] == pre[i]]\n",
    "            res = n + 1\n",
    "            for sub in combinations(nex, min(k, len(nex))):\n",
    "                res = min(res, 1 + dfs(state | sum([1 << i for i in sub])))\n",
    "            return res\n",
    "\n",
    "        pre = [0] * n\n",
    "\n",
    "        for i, j in relations:\n",
    "            pre[j - 1] |= 1 << (i - 1)\n",
    "\n",
    "        return dfs(0)\n",
    "\n",
    "# 作者：liupengsay\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        d = [0] * (n + 1)\n",
    "        for x, y in relations:\n",
    "            d[y] |= 1 << x\n",
    "        q = deque([(0, 0)])\n",
    "        vis = {0}\n",
    "        while q:\n",
    "            cur, t = q.popleft()\n",
    "            if cur == (1 << (n + 1)) - 2:\n",
    "                return t\n",
    "            nxt = 0\n",
    "            for i in range(1, n + 1):\n",
    "                if (cur & d[i]) == d[i]:\n",
    "                    nxt |= 1 << i\n",
    "            nxt ^= cur\n",
    "            if nxt.bit_count() <= k:\n",
    "                if (nxt | cur) not in vis:\n",
    "                    vis.add(nxt | cur)\n",
    "                    q.append((nxt | cur, t + 1))\n",
    "            else:\n",
    "                x = nxt\n",
    "                while nxt:\n",
    "                    if nxt.bit_count() == k and (nxt | cur) not in vis:\n",
    "                        vis.add(nxt | cur)\n",
    "                        q.append((nxt | cur, t + 1))\n",
    "                    nxt = (nxt - 1) & x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre1 = [0] * n\n",
    "        for x, y in relations:\n",
    "            pre1[y - 1] |= 1 << (x - 1)  # y 的先修课程集合，下标改从 0 开始\n",
    "\n",
    "        u = (1 << n) - 1  # 全集\n",
    "        @cache  # 记忆化搜索\n",
    "        def dfs(i: int) -> int:\n",
    "            if i == 0:  # 空集\n",
    "                return 0\n",
    "            ci = u ^ i  # i 的补集\n",
    "            i1 = 0\n",
    "            for j, p in enumerate(pre1):\n",
    "                if i >> j & 1 and p | ci == ci:  # p 在 i 的补集中，可以学（否则这学期一定不能学）\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:  # 如果个数小于 k，则可以全部学习，不再枚举子集\n",
    "                return dfs(i ^ i1) + 1\n",
    "            res = inf\n",
    "            j = i1\n",
    "            while j:  # 枚举 i1 的子集 j\n",
    "                if j.bit_count() == k:\n",
    "                    res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def bit_count(self, n: int):\n",
    "        return str(bin(n)).count('1')\n",
    "\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        d = [0] * (n + 1)\n",
    "        for pre, cur in relations:\n",
    "            d[cur] |= 1 << pre\n",
    "\n",
    "        que = deque([(0, 0)])  # 初始队列[已上课的节点数目，时间]\n",
    "        vis = {0}\n",
    "        while que:\n",
    "            cur, t = que.popleft()\n",
    "            if cur == (1 << (n + 1)) - 2:\n",
    "                return t\n",
    "\n",
    "            nxt = 0\n",
    "            for i in range(1, n + 1):\n",
    "                if (cur & d[i]) == d[i]:\n",
    "                    nxt |= 1 << i\n",
    "\n",
    "            nxt ^= cur\n",
    "            if self.bit_count(nxt) <= k:\n",
    "                if (nxt | cur) not in vis:\n",
    "                    vis.add(nxt | cur)\n",
    "                    que.append((nxt | cur, t + 1))\n",
    "            else:\n",
    "                x = nxt\n",
    "                while nxt:\n",
    "                    if self.bit_count(nxt) == k and (nxt | cur) not in vis:\n",
    "                        vis.add(nxt | cur)\n",
    "                        que.append((nxt | cur, t + 1))\n",
    "                    nxt = (nxt - 1) & x\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        parent=[0 for _ in range(n+1)]\n",
    "        for x,y in relations:\n",
    "            parent[y]|=1<<x\n",
    "        queue=[(0,0)] #第一个零的二进制表示所有的课是否上过，第二个零代表学期数\n",
    "        visited={0}#这个零的二进制代表这种情况在之前有没有出现过，如果出现过直接剪枝\n",
    "        while queue:\n",
    "            current_state,time=queue.pop(0)\n",
    "            if current_state==(1<<n+1)-2:\n",
    "                #所有课都上过了\n",
    "                return time\n",
    "\n",
    "            next_state=0 #下一次上课的状态\n",
    "            for i in range(1,n+1):\n",
    "                if (current_state&parent[i])==parent[i]:\n",
    "                    #当前状态满足了某门课的前置课程\n",
    "                    next_state|=1<<i\n",
    "                    #在下一次的上课状态中加入他的后续课程\n",
    "            next_state^=current_state\n",
    "            #next_state应该只包含新上的课，不然无法判断新上的课是否满足数量要求\n",
    "            if next_state.bit_count()<=k:\n",
    "                #能够同时上掉这些课\n",
    "                if (next_state|current_state) not in visited:\n",
    "                    #这个情况之前要是进行过的话就不进行了\n",
    "                    visited.add(next_state|current_state)\n",
    "                    queue.append((next_state|current_state,time+1))\n",
    "            else:\n",
    "                state_copy=next_state\n",
    "                while next_state:\n",
    "                    if next_state.bit_count()==k and (next_state|current_state)not in visited:\n",
    "                        visited.add(next_state|current_state)\n",
    "                        queue.append((next_state|current_state,time+1))\n",
    "                    next_state=(next_state-1)&state_copy\n",
    "            \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "def select_k_from_n(next_cour, k):\n",
    "    possible_cour = [c for c, cb in enumerate(next_cour) if (c > 0) and (cb == 0)]\n",
    "    N_pc = len(possible_cour)\n",
    "    if N_pc <= k:\n",
    "        return [possible_cour]\n",
    "    select_idx = [i for i in range(k)]\n",
    "    possible_cour_list = []\n",
    "    while True:\n",
    "        possible_cour_list.append([possible_cour[si] for si in select_idx])\n",
    "        pos_change = -1\n",
    "        while select_idx[pos_change] == N_pc + pos_change:\n",
    "            pos_change -= 1\n",
    "            if pos_change < -k:\n",
    "                return possible_cour_list\n",
    "        new_select = select_idx[pos_change] + 1\n",
    "        for p in range(pos_change, 0):\n",
    "            select_idx[p] = new_select + p - pos_change\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        comb_min_semi = {0: 0} # minimal semister that achieves course comb\n",
    "\n",
    "        comb_next_cour = {0: [0 for _ in range(n+1)]} # possible course from current comb, 0 means possible\n",
    "        cour_next_cour = defaultdict(lambda: [])\n",
    "        for a, b in relations:\n",
    "            comb_next_cour[0][b] += 1\n",
    "            cour_next_cour[a].append(b)\n",
    "\n",
    "        cms_heap = [(0, 0)]\n",
    "        while True:\n",
    "            min_semi, comb = heapq.heappop(cms_heap)\n",
    "            if (comb in comb_min_semi) and (comb_min_semi[comb] < min_semi):\n",
    "                continue\n",
    "            if comb == (1<<n) - 1:\n",
    "                return min_semi\n",
    "\n",
    "            for cour_delta in select_k_from_n(comb_next_cour[comb], k):\n",
    "                comb_delta = sum([1<<(c-1) for c in cour_delta])\n",
    "                comb_new = comb + comb_delta\n",
    "                if (comb_new not in comb_min_semi) or (comb_min_semi[comb_new] > min_semi + 1):\n",
    "                    comb_min_semi[comb_new] = min_semi + 1\n",
    "                    heapq.heappush(cms_heap, (min_semi + 1, comb_new))\n",
    "                    if comb_new not in comb_next_cour: # cal comb_next_cour\n",
    "                        comb_next_cour[comb_new] = [c_before for c_before in comb_next_cour[comb]]\n",
    "                        for c in cour_delta:\n",
    "                            comb_next_cour[comb_new][c] = -1\n",
    "                            for b in cour_next_cour[c]:\n",
    "                               comb_next_cour[comb_new][b] -= 1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre = defaultdict(set) # 前置课程，默认用集合存储\n",
    "        for x, y in relations: # y 的先修课程集合\n",
    "            pre[y].add(x)\n",
    "        U = frozenset(range(1, n+1)) #所有课程集合。这里 frozenset 是冻结的集合，因为 set 本身是动态的，不可哈希，没办法用 cache 记忆化。\n",
    "        q = [(U, 0)]\n",
    "        memo = {}\n",
    "\n",
    "        while q:\n",
    "            to_study, state = q.pop()\n",
    "            if to_study in memo:\n",
    "                continue\n",
    "\n",
    "        \n",
    "            if to_study == set(): \n",
    "                memo[to_study] = 0\n",
    "                continue\n",
    "\n",
    "            already_study = U - to_study\n",
    "            candidate = set() # 候选集合，这里用set，因为要往里塞可以上的课，动态集合\n",
    "            for t in to_study: # 遍历要学的课，选出马上可以学的\n",
    "                if pre[t] | already_study == already_study:\n",
    "                    candidate.add(t) # 塞进去候选者\n",
    "            if len(candidate) <= k: # 小于 k 门，直接学\n",
    "                if state == 0:\n",
    "                    q.append((to_study, 1))\n",
    "                    q.append((to_study-candidate, 0))\n",
    "                    continue\n",
    "                else:\n",
    "                    memo[to_study] = memo[to_study-candidate] + 1\n",
    "                    continue\n",
    "            res = float('inf')\n",
    "\n",
    "            if state == 0:\n",
    "                q.append((to_study, 1))\n",
    "\n",
    "            for c in combinations(candidate, k):\n",
    "                c = frozenset(c)\n",
    "                if state == 0:\n",
    "                    q.append((to_study-c, 0))\n",
    "                else:\n",
    "                    res = min(res, memo[to_study-c])\n",
    "            if state:\n",
    "                memo[to_study] = res + 1\n",
    "\n",
    "        return memo[U]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre = defaultdict(set) # 前置课程，默认用集合存储\n",
    "        for x, y in relations: # y 的先修课程集合\n",
    "            pre[y].add(x)\n",
    "        U = frozenset(range(1, n+1)) #所有课程集合。这里 frozenset 是冻结的集合，因为 set 本身是动态的，不可哈希，没办法用 cache 记忆化。\n",
    "        q = [(U, [])]\n",
    "        memo = {}\n",
    "\n",
    "        while q:\n",
    "            to_study, argue = q.pop()\n",
    "            if to_study in memo:\n",
    "                continue\n",
    "\n",
    "            if to_study == set(): \n",
    "                memo[to_study] = 0\n",
    "                continue\n",
    "            \n",
    "            if len(argue) > 0:\n",
    "                memo[to_study] = min(memo[x] for x in argue) + 1\n",
    "            else:\n",
    "                already_study = U - to_study\n",
    "                candidate = set() # 候选集合，这里用set，因为要往里塞可以上的课，动态集合\n",
    "                for t in to_study: # 遍历要学的课，选出马上可以学的\n",
    "                    if pre[t] | already_study == already_study:\n",
    "                        candidate.add(t) # 塞进去候选者\n",
    "                if len(candidate) <= k: # 小于 k 门，直接学\n",
    "                    q.append((to_study, [frozenset(to_study-candidate)]))\n",
    "                    q.append((to_study-candidate, []))\n",
    "                    continue\n",
    "\n",
    "                for c in combinations(candidate, k):\n",
    "                    c = frozenset(c)\n",
    "                    argue.append(to_study-c)\n",
    "\n",
    "                q.append((to_study, argue))\n",
    "                for a in argue:\n",
    "                    q.append((a, []))\n",
    "                    \n",
    "        return memo[U]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre = defaultdict(set) # 前置课程，默认用集合存储\n",
    "        for x, y in relations: # y 的先修课程集合\n",
    "            pre[y].add(x)\n",
    "        U = frozenset(range(1, n+1)) #所有课程集合。这里 frozenset 是冻结的集合，因为 set 本身是动态的，不可哈希，没办法用 cache 记忆化。\n",
    "        q = [(U, [])]\n",
    "        memo = {}\n",
    "\n",
    "        while q:\n",
    "            to_study, argue = q.pop()\n",
    "            if to_study in memo:\n",
    "                continue\n",
    "\n",
    "            if to_study == set(): \n",
    "                memo[to_study] = 0\n",
    "                continue\n",
    "            \n",
    "            if len(argue) > 0:\n",
    "                memo[to_study] = min(memo[x] for x in argue) + 1\n",
    "            else:\n",
    "                already_study = U - to_study\n",
    "                candidate = set() # 候选集合，这里用set，因为要往里塞可以上的课，动态集合\n",
    "                for t in to_study: # 遍历要学的课，选出马上可以学的\n",
    "                    if pre[t] | already_study == already_study:\n",
    "                        candidate.add(t) # 塞进去候选者\n",
    "                if len(candidate) <= k: # 小于 k 门，直接学\n",
    "                    q.append((to_study, [frozenset(to_study-candidate)]))\n",
    "                    q.append((to_study-candidate, []))\n",
    "                    continue\n",
    "\n",
    "                for c in combinations(candidate, k):\n",
    "                    c = frozenset(c)\n",
    "                    argue.append(to_study-c)\n",
    "\n",
    "                q.append((to_study, argue))\n",
    "                for a in argue:\n",
    "                    q.append((a, []))\n",
    "                    \n",
    "        return memo[U]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        u = (1 << n) - 1\n",
    "        pre = [0] * n\n",
    "        for a, b in relations:\n",
    "            pre[b - 1] |= (1 << (a - 1))\n",
    "        @cache\n",
    "        def dfs(i):\n",
    "            if i == 0: return 0\n",
    "            cui = u ^ i\n",
    "            i1 = 0\n",
    "            res = inf\n",
    "            for j, val in enumerate(pre):\n",
    "                if i >> j & 1 and val | cui == cui:\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k: return dfs(i ^ i1) + 1\n",
    "            j = i1 - 1\n",
    "            while j:\n",
    "                if j.bit_count() <= k: res = min(res, dfs(i ^ j) + 1)\n",
    "                j = (j - 1) & i1\n",
    "            return res\n",
    "        return dfs(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre = [0] * n\n",
    "        for i in relations:\n",
    "            pre[i[1] - 1] |= (1 << i[0] - 1)\n",
    "        all = (1 << n) - 1\n",
    "\n",
    "        @cache\n",
    "        def dfs(cur: int) -> int:\n",
    "            if cur == 0:\n",
    "                return 0\n",
    "            nonlocal all, pre\n",
    "            curRange = 0\n",
    "            cur_learned = all ^ cur\n",
    "            for curPreIndex in range(len(pre)):\n",
    "                if (cur >> curPreIndex & 1 == 1) and cur_learned & pre[curPreIndex] == pre[curPreIndex]:\n",
    "                    curRange |= (1 << curPreIndex)\n",
    "            if curRange.bit_count() <= k:\n",
    "                return dfs(cur ^ curRange) + 1\n",
    "\n",
    "            res = inf\n",
    "            index = curRange\n",
    "            while index:\n",
    "                if index.bit_count() <= k:\n",
    "                    res = min(res, dfs(cur ^ index) + 1)\n",
    "                index = (index - 1) & curRange\n",
    "            return res\n",
    "\n",
    "        return dfs(all)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre = [0]*n\n",
    "        for x,y in relations:\n",
    "            pre[y - 1] |= 1 << (x - 1)\n",
    "        u = (1 << n) - 1 # 全部课程\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i):# 修集合i全部课程需要的天数\n",
    "            if i == 0:\n",
    "                return 0\n",
    "            ci = u ^ i # 集合i的补集\n",
    "            i1 = 0 # 枚举可以直接修的i的子集（要求课程j必须在i里，且j的前置课程不在i里）\n",
    "            for j,p in enumerate(pre):\n",
    "                if i >> j & 1 and p | ci == ci:# 如果j是i的子集 并且 pre[j] 在i的补集里\n",
    "                    i1 |= 1 << j\n",
    "            if i1.bit_count() <= k:# 子集元素个数小于k，直接学习\n",
    "                return dfs(i & ~i1) + 1\n",
    "            ans = inf\n",
    "            j = i1\n",
    "            while j: # 1天修不完，枚举i1的子集\n",
    "                if j.bit_count() <= k:\n",
    "                    ans = min(ans,dfs(i ^ j) + 1)\n",
    "                j = i1 & (j - 1)\n",
    "            return ans\n",
    "        \n",
    "        return dfs(u)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "       pre = [0] * n\n",
    "       u = (1 << n) - 1\n",
    "       for r in relations:\n",
    "          pre[r[1] - 1] |= 1 << (r[0] - 1)\n",
    "\n",
    "       @cache\n",
    "       def dfs(i: int) -> int:\n",
    "          if i == u:\n",
    "             return 0\n",
    "          c = u ^ i\n",
    "          candidate = 0\n",
    "          while c:\n",
    "             index = (c & -c).bit_length() - 1\n",
    "             if (pre[index] | i) == i:\n",
    "                candidate |= 1 << index\n",
    "             c &= c - 1\n",
    "          if candidate.bit_count() <= k:\n",
    "             return dfs(i | candidate) + 1\n",
    "          res = inf\n",
    "          j = candidate\n",
    "          while j:\n",
    "             if j.bit_count() <= k:\n",
    "                res = min(res, dfs(i | j) + 1)\n",
    "             j = (j - 1) & candidate\n",
    "          return res\n",
    "       return dfs(0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        #建图\n",
    "        grap=[[]for i in range(n+1)]\n",
    "        ru=[0]*(n+1)\n",
    "        for x,y in relations:\n",
    "            grap[x].append(y)\n",
    "            ru[y]+=1\n",
    "        \n",
    "        def getZJ(lt,l):\n",
    "            if len(lt)==l:\n",
    "                return [lt]\n",
    "            if len(lt)<l:\n",
    "                return []\n",
    "            \n",
    "            ans=[]\n",
    "            if l==1:\n",
    "                for i in lt:\n",
    "                    ans.append([i])\n",
    "                return ans\n",
    "            for i in range(len(lt)):\n",
    "                nlt=lt[i+1:]\n",
    "                if len(nlt)>=l-1:\n",
    "                    t=getZJ(nlt,l-1)\n",
    "                    for j in t:\n",
    "                        ans.append([lt[i]]+j)\n",
    "            return ans\n",
    "        @cache\n",
    "        def f(lt,rudu):\n",
    "            #找集合中 入度为0的点\n",
    "            # print(\"lt\",lt)\n",
    "            # print(\"rudu\",rudu)\n",
    "            # print(\"====\")\n",
    "            lt=list(lt)\n",
    "            rudu=list(rudu)\n",
    "            ru0,runo0=list(),list()\n",
    "            for p in lt:\n",
    "                if rudu[p]==0:\n",
    "                    ru0.append(p)\n",
    "                else:\n",
    "                    runo0.append(p)\n",
    "            if len(lt)==0:\n",
    "                return 0\n",
    "            if len(ru0)<=k:\n",
    "                for p in ru0:\n",
    "                    for nex in grap[p]:\n",
    "                        rudu[nex]-=1\n",
    "                return f(tuple(runo0),tuple(rudu))+1\n",
    "            else:#学k门 留l-k门不学\n",
    "                ZJ=getZJ(ru0,k) #求子集 表示要学的 和不学的\n",
    "                ans=inf\n",
    "                for xue in ZJ:\n",
    "                    noxue=list()\n",
    "                    for p in ru0:\n",
    "                        if p not in xue:\n",
    "                            noxue.append(p)\n",
    "                    new_rudu=rudu.copy()\n",
    "                    for p in xue:\n",
    "                        for nex in grap[p]:\n",
    "                            new_rudu[nex]-=1\n",
    "                    ans=min(f(tuple(noxue+runo0),tuple(new_rudu))+1,ans)\n",
    "                return ans\n",
    "        ke=[i for i in range(1,n+1)]\n",
    "\n",
    "        return f(tuple(ke),tuple(ru))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        map1=defaultdict(int)\n",
    "        def dfs(stat,rest):\n",
    "            nonlocal map1,k,n,need\n",
    "            if map1[(stat,rest)]!=0:\n",
    "                return map1[(stat,rest)]\n",
    "            if rest==0 and stat!=0:\n",
    "                return 1+dfs(stat,k)\n",
    "            if rest==k:\n",
    "                cnt=0\n",
    "                tmp=stat\n",
    "                for i in range(n):\n",
    "                    if (stat&(1<<i))!=0 and (stat&(need[i]))==0:\n",
    "                        cnt+=1\n",
    "                        tmp=tmp-(1<<i)\n",
    "                if cnt<=k and tmp!=0:\n",
    "                    return 1+dfs(tmp,k)\n",
    "                if cnt<=k and tmp==0:\n",
    "                    return 1\n",
    "            \n",
    "            res=n+1\n",
    "            for i in range(n):\n",
    "                if (stat&(1<<i))!=0 and (stat&(need[i]))==0:\n",
    "                    res=min(dfs(stat-(1<<i),rest-1),res)\n",
    "            map1[(stat,rest)]=res\n",
    "            return res\n",
    "        need=[0]*n\n",
    "        for r in relations:\n",
    "            need[r[1]-1]=(need[r[1]-1])|(1<<(r[0]-1))\n",
    "        return dfs((1<<n)-1,k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import inf \n",
    "from typing import List\n",
    "from functools import cache\n",
    "from collections import defaultdict\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre = defaultdict(set)\n",
    "        for x, y in relations:\n",
    "            pre[y].add(x)\n",
    "        U = frozenset(range(1, n+1))\n",
    "        @cache\n",
    "        def f(to_study:frozenset):\n",
    "            if to_study == set():\n",
    "                return 0\n",
    "            already_study = U - to_study\n",
    "            candidate = set()\n",
    "            for t in to_study:\n",
    "                if pre[t] | already_study == already_study:\n",
    "                    candidate.add(t)\n",
    "            if len(candidate) <= k:\n",
    "                return f(to_study-candidate) + 1\n",
    "            res = float('inf')\n",
    "            for c in combinations(candidate, k):\n",
    "                c = frozenset(c)\n",
    "                res = min(res, f(to_study-c) + 1)\n",
    "            return res\n",
    "        return f(U)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from functools import cache\n",
    "from collections import defaultdict\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def minNumberOfSemesters(self, n: int, relations: List[List[int]], k: int) -> int:\n",
    "        pre = defaultdict(set) # 前置课程，默认用集合存储\n",
    "        for x, y in relations: # y 的先修课程集合\n",
    "            pre[y].add(x)\n",
    "        U = frozenset(range(1, n+1)) #所有课程集合。这里 frozenset 是冻结的集合，因为 set 本身是动态的，不可哈希，没办法用 cache 记忆化。\n",
    "        @cache\n",
    "        def f(to_study:frozenset): # to_study 意为要去学的集合\n",
    "            if to_study == set(): # 边界条件，没课程学了，花费 0 天\n",
    "                return 0\n",
    "            already_study = U - to_study # 已经学的，这里 - 号直接取差集，很方便\n",
    "            candidate = set() # 候选集合，这里用set，因为要往里塞可以上的课，动态集合\n",
    "            for t in to_study: # 遍历要学的课，选出马上可以学的\n",
    "                if pre[t] | already_study == already_study:\n",
    "                    candidate.add(t) # 塞进去候选者\n",
    "            if len(candidate) <= k: # 小于 k 门，直接学\n",
    "                return f(to_study-candidate) + 1 # 幸好 python 中，frozenset 类型 - set 类型 = frozenset 类型，保证参数可以哈希\n",
    "            res = float('inf')\n",
    "            for c in combinations(candidate, k): # 要从所有候选课里选出k门在这学期学，直接调用 python combinations 很方便\n",
    "                c = frozenset(c) # c 本身是元祖，转化成 frozenset 或 set，这里选择 frozenset\n",
    "                res = min(res, f(to_study-c) + 1)\n",
    "            return res\n",
    "        return f(U) # 要学所有的课需要的学期数\n",
    "\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
